5255. Цифра

Васе надоело складывать числа и он занялся изучением их свойств. В данный момент его интересует вопрос: какая цифра в записи числа встречается наиболее часто? Если таких цифр несколько, он выбирает меньшую из них.

Какую же цифру выбрал Вася в очередном числе?

Вход. Одно число, рассматриваемое Васей. Количество цифр в десятичной записи числа не превышает 10⁵.

Выход. Вывести цифру, выбранную Васей.

Пример входа	Пример выхода
14221321	1

РЕШЕНИЕ

сортировка подсчетом

Анализ алгоритма

При помощи сортировки подсчетом в массиве cnt подсчитаем количество каждой цифры во входном числе. Далее найдем какая цифра в cnt встречается чаще всего.

Реализация алгоритма

Входное число считываем в массив s. Объявим массив cnt для подсчета цифр.

char s[100010];

int cnt[10];

Читаем входную строку.

gets(s);

Подсчитываем количество каждой цифры в числе: cnt[i] хранит количество цифр i, которое встречается во входном числе.

for (i = 0; i < strlen(s); i++)

cnt[s[i] - '0']++;

Находим максимальное значение в массиве cnt. В переменной ptr запоминаем цифру, которая встречается чаще всего.

max = ptr = -1;

for (i = 0; i < 10; i++)

if (cnt[i] > max)

{

max = cnt[i];

ptr = i;

}

Выводим чаще всего встречаемую цифру.

printf("%d\n", ptr);